package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC926 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minFlipsMonoIncr(String s) {
            int[] zeroCnt = new int[s.length() + 1];
            int[] oneCnt = new int[s.length() + 1];
            zeroCnt[0] = s.charAt(0) == '0' ? 1 : 0;
            oneCnt[0] = s.charAt(0) == '1' ? 1 : 0;

            for (int i = 1; i < s.length(); i++) {
                zeroCnt[i] = zeroCnt[i - 1] + (s.charAt(i) == '0' ? 1 : 0);
                oneCnt[i] = oneCnt[i - 1] + (s.charAt(i) == '1' ? 1 : 0);
            }

            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < s.length(); i++) {
                // 从i位置到end结束的闭区间，全部的0翻转1
                int shouldFlipToOneCnt = zeroCnt[s.length() - 1] - (i == 0 ? 0 : zeroCnt[i - 1]);
                // 从0到i-1位置的闭区间，全部的1翻转0
                int shouldFlipToZeroCnt = i == 0 ? 0 : oneCnt[i - 1];
                ans = Math.min(ans, shouldFlipToOneCnt + shouldFlipToZeroCnt);
            }

            return Math.min(ans, oneCnt[s.length() - 1]);// 再比上全部翻转为0的方案
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.minFlipsMonoIncr("00110"));
        System.out.println(solution.minFlipsMonoIncr("010110"));
        System.out.println(solution.minFlipsMonoIncr("00011000"));
    }

    public static void main(String[] args) throws Exception {
        LC926 an = new LC926();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
